沉下心来分析HashMap的源码（二）
HashMap的源码在JDK 1.8 的Put和Remove操作。
/**
* Implements Map.put and related methods.
* put逻辑：
* 1. 检查hashmap中的table是否需要扩容
* 2.1 确定放入的值的位置：(n - 1) & hash，hash的计算方式：(h = key.hashCode()) ^ (h >>> 16)
* 2.2 如果该位置没有值，直接的新建Node，设置key，value值，放入table
* 2.3 如果该位置有Node值，判断key值有否相同
* 2.3.1 相同则是替换value值
* 2.3.2 不相同则是判断Node值的类型
* 2.3.2.1 如果Node值的类性是：TreeNode，标识为一颗红黑树的类型，调用putTreeVal
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n,/* n 代表的是原始的hashmap中 table 的 length值*/ i;
if ((tab = table) == null || (n = tab.length) == 0)
//扩容
n = (tab = resize()).length;
// & 值的运算：得到的值只可能比n-1小,如果table[i]为null,直接的赋值即可。
if ((p = tab[i = (n - 1) & hash]) == null) //①
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
// p=table[i]; hash值相同，k值和p的key值一样，直接的替换
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//②
//替换value值
e = p;
else if (p instanceof TreeNode)//③
// 如果有值，并且Node的类型是TreeNode类型，调用TreeNode的putTreeVal
// TODO 暂时的放弃这个分支的分析
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// ④
// 如果不是TreeNode，那就是一个链表的类型
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果达到了7个，开始变换数据结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//传入的参数竟然是table和hash值
treeifyBin(tab, hash);
break;
}
//4.2
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
这里面最重要的就是③ 和 ④ 两种情况，其中4种的 treeifyBin(tab, hash) 会首先被触发，在链表元素为七的时候，也就是：
k0 -> k1 -> k2 -> k3 -> k4 -> k5 -> k6
在k6 加入的时候，节点到达了7个的时候，触发：treeifyBin
public final void treeifyBin(Node<K,V>[] tab, int hash) {
this.table = tab;
int n, index; Node<K,V> e;
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
if (tab == null || (n = tab.length) < 1)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 先把Node节点全部的转化为TreeNode节点
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 此时的hd为0->1->2->3->...->end 为链表的数据结构
if ((tab[index] = hd) != null)
// 链状的TreeNode节点转为为树状
hd.treeify(tab);
}
}
这个方法最主要的一点是通过一个 do while 循环把Node节点转化为TreeNode节点，然后进行红黑树转化，调用：treeify。
从这里我们可以得到③的类型判断的逻辑了，如果节点是TreeNode节点的类型，那么数组内存储的就是一个红黑树了：
if (p instanceof TreeNode)
直接的调用，红黑树的插入操作了：
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
关于红黑树的逻辑，我们下篇接着说，这篇我们主要集中在Map的数据结构。
最后还有一个推测：从这里我们可以推测remove的逻辑，当TreeNode的节点少于8个，也就是7个的时候，调用链表话的操作，再次转化数据结构吗？
REMOVE操作
直接上代码：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
hash 算法为同一个算法
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// finde node value
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// !matchValue || (v = node.value) == value
// node为key值对应的节点，p为key的前一个节点
if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
// node 为当前的节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
// afterNodeRemoval(node);
return node;
}
}
return null;
}
像比较PUT的逻辑来说，Remove操作，首先要找到删除的节点，然后根据删除节点所在的数组中存储节点的类型，来进行确定，是进行链表的删除操作，还是红黑树的节点删除操作。
节点的转化，肯定在红黑的删除操作中，由于红黑树的删除的操作比较的复杂，所以我们直接看我们关心的逻辑即可：
final void removeTreeNode(MyMap<K,V> map, Node<K,V>[] tab,boolean movable) {
。。。。。。。。
if (root == null || (movable&& (root.right == null|| (rl = root.left) == null || rl.left == null))) {
// 由树转化为链表的数据结构
tab[index] = first.untreeify(map); // too small
return;
}
。。。。。。。
判断也比较有意思
final Node<K,V> untreeify(MyMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;//⑤
tl = p;
}
return hd;
}
从代码中可以看到，确实和我们预料的情况一样。在一定的条件下，树直接退化为链表数据结构。
关于红黑树的操作，HashMap的操作，也和普通的红黑树不一样，准确的说，是比普通的红黑树复杂，因为涉及到树节点集成的next， 和自己定义的pre指向的保持，不然也不会有 树直接退化为链表 的方法untreeify 的操作⑤标注的next操作。具体是如何的维持，我们下篇再说。